﻿/*
题目：缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

https://leetcode.cn/problems/first-missing-positive/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 长度为 n 的数组，最小的正整数一定出现在 [1, n] 里面
    // 2, 1, 3, 4
    // 0, 1, 2, 3
    // 覆盖法：保证 [1, n] 里面的元素都在自己下标的位置上

    int firstMissingPositive(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int n = nums.size();

        // 将 [1, n] 都调整到对应的下标里面
        while (left <= right) {
            // 如果这个元素不在目标区间里面, 那么将这个元素移到最右边
            if (nums[left] <= 0 || nums[left] > n) {
                swap(nums[left], nums[right]);
                right--;
                continue;
            }

            // 如果这个元素就是区间中的元素 [1, n], 就调到对应的下标
            // 并且要求：如果该位置本来就是正确的了，那么不让改
            if (nums[left] - 1 != left && nums[nums[left] - 1] != nums[left]) {
                swap(nums[left], nums[nums[left] - 1]);
            }
            else {
                left++;
            }
        }


        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)   return i + 1;
        }

        // [1, n] 最好的情况都找不到，直接返回 n + 1
        return n + 1;
    }
};

